home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / DCLAP 6d / dclap6d / DClap / DRunArray.cpp < prev    next >
Text File  |  1996-07-05  |  11KB  |  369 lines
  1. // DRunArray.cpp
  2. // d.g.gilbert
  3.  
  4.  
  5. // DRunArray.h
  6. // d.g.gilbert
  7.  
  8. #ifndef _DRUNARRAY_
  9. #define _DRUNARRAY_
  10.  
  11. class DRunArray 
  12. {
  13. public:
  14.         enum { kIndexBad = 0, kIndexFirst    = 1, kIndexLast = 0x7FFFFFFF };
  15.                           
  16.         DRunArray();
  17.         virtual ~DRunArray( long inItemSize);
  18.         
  19.         //virtual Nlm_Boolean selected(long index);
  20.         //virtual void select(long index);
  21.         //virtual void select(long start, long finish);
  22.         
  23.         //virtual void set(long index, long value);
  24.         //virtual void set(long start, long finish, long value);
  25.         //virtual long get(long index);
  26.         
  27.         virtual void* getItemPtr( long itemIndex) const;
  28.         virtual void InsertItemsAt( long inCount, long inAtIndex,
  29.                                                     const void *inItem, long inItemSize);
  30.         virtual void RemoveItemsAt( long inCount, long inAtIndex);
  31.         virtual void AssignItemsAt( long inCount, long inAtIndex, 
  32.                                                     const void *inValue, long inItemSize);
  33.         Boolean goodIndex(long index) 
  34.             { 
  35.             return (index >= kIndexFirst && index <= kIndexLast); 
  36.             } 
  37.         
  38. protected:
  39.         long * fRuns;
  40.         char * fValues;
  41.         long     fNruns, fNitems, fValueSize;
  42.         struct RunRec { long    start, end; };
  43.  
  44.         long     getRunIndex( long itemIndex);
  45.         void* getRunItemPtr( long runIndex) const 
  46.             { 
  47.             return (fValues + fValueSize * runIndex); 
  48.             }
  49.         long getRunStart( long runIndex) const
  50.             {
  51.             return (((RunRec*)(fRuns))[runIndex].start);
  52.             }
  53.  
  54.         void InsertRun( long inRunIndex, long inCount, const void *inItem);
  55.         void SplitRun( long inRunIndex, long inItemIndex, long inCount, const void *inItem);
  56.         void ExtendRun( long inRunIndex, long inCount);
  57. };
  58.  
  59.  
  60. #endif /* _DRUNARRAY_ */
  61.  
  62.  
  63.  
  64. #include "DRunArray.h"
  65. #include <ncbi.h>
  66. #include <dgg.h>
  67.  
  68.  
  69. DRunArray::DRunArray( long inItemSize) :
  70.     fRuns(NULL), fValues(NULL),
  71.     fNruns(0), fNitems(0), fValueSize(inItemSize)
  72. {
  73. }
  74.  
  75.  
  76.  
  77. DRunArray::~DRunArray()
  78. {
  79.     MemFree(fRuns);
  80.     MemFree(fValues);
  81. }
  82.  
  83.  
  84. //    Insert new items into a RunArray at the specified index
  85.  
  86. void DRunArray::InsertItemsAt( long inCount, long inAtIndex,
  87.                         const void *inItem, long inItemSize)
  88. {
  89.     if (inAtIndex > fNitems) inAtIndex = fNitems + 1;  
  90.     else if (inAtIndex < 1) inAtIndex = 1;
  91.     
  92.     if (fNitems == 0)  
  93.         InsertRun(0, inCount, inItem);
  94.         
  95.             // append to array
  96.     else if (inAtIndex > fNitems) {
  97.         if (Nlm_MemCmp( inItem, getRunItemPtr(fNruns-1), fValueSize) == 0) 
  98.             ExtendRun(fNruns - 1, inCount);  
  99.         else 
  100.             InsertRun(fNruns, inCount, inItem);
  101.         } 
  102.         
  103.             // insert at start of array
  104.     else if (inAtIndex == 1) {     
  105.         if (Nlm_MemCmp(inItem, getRunItemPtr(0), fValueSize) == 0)  
  106.             ExtendRun(0, inCount);  
  107.         else 
  108.             InsertRun(0, inCount, inItem);
  109.         } 
  110.         
  111.         // insert in middle
  112.     else {     
  113.         long    withinRun = getRunIndex(inAtIndex);
  114.         if (Nlm_MemCmp(inItem, getRunItemPtr(withinRun), fValueSize) == 0)  
  115.             ExtendRun(withinRun, inCount); 
  116.         else if (inAtIndex == getRunStart(withinRun)) {
  117.             if (Nlm_MemCmp(inItem, getRunItemPtr(withinRun - 1), fValueSize) == 0) 
  118.                 ExtendRun(withinRun - 1, inCount); 
  119.             else  
  120.                 InsertRun(withinRun, inCount, inItem);            
  121.             } 
  122.         else                     // Inserting into the middle of  a Run
  123.             SplitRun(withinRun, inAtIndex, inCount, inItem);
  124.         }
  125.     fNitems += inCount;
  126. }
  127.  
  128.  
  129. //    Remove items from the Array starting at the specified index
  130.  
  131. void DRunArray::RemoveItemsAt( long inCount, long inAtIndex)
  132. {
  133.     if ( goodIndex(inAtIndex) && (inCount > 0)) {
  134.     
  135.         if ((inAtIndex + inCount) > fNitems) {
  136.                                         // remove from tail
  137.             if (inAtIndex == 1) {
  138.                                         // delete all
  139.                 fValues= (char*) ::MemMore( fValues, 0);
  140.                 fRuns= (long*) ::MemMore( fRuns, 0);
  141.                 fNruns= 0;
  142.                 } 
  143.             else {
  144.                                         // Last Run will be the one containing
  145.                                         //   the item before the one being removed
  146.                 long    lastRun = getRunIndex(inAtIndex - 1);
  147.                 fValues= (char*) ::MemMore( fValues, (lastRun + 1) * fValueSize);
  148.                 fRuns= (long*) ::MemMore( fRuns, (lastRun + 1) * sizeof(RunRec));
  149.                 ((RunRec*)(fRuns))[lastRun].end = inAtIndex - 1;
  150.                 fNruns = lastRun + 1;
  151.                 }
  152.             fNitems = inAtIndex - 1;
  153.             } 
  154.         else if (inAtIndex == 1) {     
  155.                                     // remove from top
  156.                                         // First Run will be the one containing
  157.                                         //   the item after the deleted ones
  158.             long    firstRun = getRunIndex(inCount + 1);
  159.             if (firstRun > 0) {
  160.                                         // Remove Runs from start up to, but
  161.                                         //   not including, firstRun
  162.                                         // Shift down data for remaining items
  163.                 ::MemMove( getRunItemPtr(firstRun), fValues,
  164.                                     (fNruns - firstRun) * fValueSize);
  165.                                         // Shift down remaining Run records
  166.                 ::MemMove( fRuns + firstRun * sizeof(RunRec),
  167.                                     fRuns, (fNruns - firstRun) * sizeof(RunRec));
  168.                                         // Reduce sizes of data and runs handles to new number of runs
  169.                 fNruns -= firstRun;    
  170.                 fValues= (char*) ::MemMore( fValues, fNruns * fValueSize);
  171.                 fRuns= (long*) ::MemMore( fRuns, fNruns * sizeof(RunRec));
  172.                 }
  173.             
  174.                                         // Adjust indexes for first Run
  175.             RunRec    *run = (RunRec*) fRuns;
  176.             run[0].start = 1;
  177.             run[0].end -= inCount;
  178.             
  179.                                         // Adjust indexes for the second and  succeeding Runs
  180.             for (long i = 1; i < fNruns; i++) {
  181.                 run[i].start -= inCount;
  182.                 run[i].end -= inCount;
  183.                 }            
  184.             fNitems -= inCount;
  185.             } 
  186.         else {                         
  187.                         // remove from middle
  188.                                         // The Runs between, but not  including, oneEnd and twoStart  will be deleted
  189.             long oneEnd = getRunIndex(inAtIndex - 1);
  190.             long twoStart = getRunIndex(inAtIndex + inCount);
  191.             if (oneEnd == twoStart)      // Items to delete are all within  a single Run
  192.                 ((RunRec*)(fRuns))[oneEnd].end -= inCount;
  193.             else {
  194.                 ((RunRec*)(fRuns))[oneEnd].end = inAtIndex - 1;
  195.                 ((RunRec*)(fRuns))[twoStart].start = inAtIndex;
  196.                 ((RunRec*)(fRuns))[twoStart].end -= inCount;
  197.                 
  198.                 if (twoStart > (oneEnd + 1)) {
  199.                                         // Items to delete span at least  one entire Run, so one or  more Runs must be removed
  200.                                         // Shift down item data
  201.                     ::MemMove( getRunItemPtr(twoStart), getRunItemPtr(oneEnd + 1),
  202.                                     (fNruns - twoStart) * fValueSize);
  203.                                         // Shift down Run records
  204.                     ::MemMove(fRuns + twoStart * sizeof(RunRec),
  205.                                     fRuns + (oneEnd + 1) * sizeof(RunRec),
  206.                                     (fNruns - twoStart) * sizeof(RunRec));
  207.                                     
  208.                                         // Adjust sizes of item and Run Handles to new number of Runs
  209.                     fNruns -= (twoStart - oneEnd - 1);
  210.                     fValues= (char*) ::MemMore( fValues, fNruns * fValueSize);
  211.                     fRuns= (long*) ::MemMore( fRuns, fNruns * sizeof(RunRec));
  212.                                         // Removing Runs have moved twoStart next to oneEnd
  213.                     twoStart = oneEnd + 1;
  214.                     }
  215.                 }
  216.                                         // Adjust indexes for Runs after twoStart
  217.             RunRec* run = (RunRec*) mRunsH;
  218.             for (long i = twoStart + 1; i < fNruns; i++) {
  219.                 run[i].start -= inCount;
  220.                 run[i].end -= inCount;
  221.                 }
  222.             fNitems -= inCount;
  223.             }
  224.         }
  225. }
  226.  
  227. void DRunArray::AssignItemsAt( long inCount, long inAtIndex, 
  228.                     const void *inValue, long inItemSize)
  229. {
  230.     if (goodIndex(inAtIndex) && (inCount > 0)) {
  231.         RemoveItemsAt(inCount, inAtIndex);
  232.         InsertItemsAt(inCount, inAtIndex, inValue, inItemSize);
  233.         }
  234. }
  235.  
  236. void* DRunArray::getItemPtr( long itemIndex) const
  237. {
  238.     return getRunItemPtr( getRunIndex(itemIndex));
  239. }
  240.  
  241.  
  242. //---------
  243.  
  244. //    Return the index of the Run containing the specified item
  245. //    Run index is zero-based
  246.  
  247. long DRunArray::getRunIndex( long itemIndex)
  248. {
  249.     long index = kIndexBad;
  250.     RunRec* run = (RunRec*) fRuns;
  251.     for (long i = 0; i < fNruns; i++) {         
  252.         if (itemIndex <= run[i].end) {
  253.             index = i;
  254.             break;
  255.         }
  256.     }
  257.     return index;
  258. }
  259.  
  260.  
  261. //    Insert a new Run with the specified location, length, and value
  262.  
  263. void DRunArray::InsertRun( long inRunIndex, long inCount, const void *inItem)
  264. {
  265.                                         // Add room for another data item
  266.     if (fValues == NULL) 
  267.         fValues= (char*) ::MemNew((fNruns + 1) * fValueSize);
  268.     else  
  269.         fValues= (char*) ::MemMore( fValues, (fNruns+1) * fValueSize);
  270.     if (!fValues) Nlm_Message(MSG_FATAL, "DRunArray:: memory full");
  271.           
  272.                                         // Add room for another RunRec
  273.     if (fRuns == NULL)  
  274.         fRuns= (long*) ::MemNew((fNruns + 1) *  sizeof(RunRec));
  275.     else  
  276.         fRuns= (long*) ::MemMore( fRuns, (fNruns+1) *  sizeof(RunRec));
  277.     if (!fRuns) Nlm_Message(MSG_FATAL, "DRunArray:: memory full");
  278.          
  279.                                         // Adjust Run indexes
  280.     RunRec* run = (RunRec*) fRuns;
  281.     
  282.     if (fNruns == 0) {                // Array was empty
  283.         run[0].start = 1;
  284.         run[0].end = inCount;
  285.         } 
  286.     else if (inRunIndex == fNruns) {
  287.                                         // Insert at end of Array
  288.         run[fNruns].start = run[fNruns - 1].end + 1;
  289.         run[fNruns].end = run[fNruns].start + inCount - 1;
  290.         } 
  291.     else if (inRunIndex < fNruns) {
  292.                                         // Shift up item data
  293.         ::MemMove( getRunItemPtr(inRunIndex), getRunItemPtr(inRunIndex + 1),
  294.                                 (fNruns - inRunIndex) * fValueSize);
  295.                                         // Shift up run data
  296.         ::MemMove(fRuns + inRunIndex * sizeof(RunRec),
  297.                         fRuns + (inRunIndex + 1) * sizeof(RunRec),
  298.                         (fNruns - inRunIndex) * sizeof(RunRec));
  299.         run[inRunIndex].end = run[inRunIndex].start + inCount - 1;
  300.         }
  301.     
  302.                                         // Shift up indexes of Runs past insertion point
  303.     fNruns += 1;
  304.     for (long i = inRunIndex + 1; i < fNruns; i++) {
  305.         run[i].start += inCount;
  306.         run[i].end += inCount;
  307.         }
  308.     
  309.                                         // Store data for new items
  310.     ::MemMove(inItem, getRunItemPtr(inRunIndex), fValueSize);
  311. }
  312.  
  313.  
  314.  
  315. //    Insert a new Run into the middle of an existing Run, thereby splitting
  316. //    the existing Run into two pieces.
  317.  
  318. void DRunArray::SplitRun( long inRunIndex, long inItemIndex, long inCount, const void *inItem)
  319. {
  320.                                         // Add room for two data items
  321.     fValues= (char*) ::MemMore( fValues, (fNruns + 2) * fValueSize);
  322.     if (!fValues) Nlm_Message(MSG_FATAL, "DRunArray:: memory full");
  323.                                         // Add room for two RunRecords
  324.     fRuns= (long*) ::MemMore( fRuns, (fNruns + 2) * sizeof(RunRec));
  325.     if (!fRuns) Nlm_Message(MSG_FATAL, "DRunArray:: memory full");
  326.     
  327.     RunRec    *run = (RunRec*) fRuns;
  328.     if (inRunIndex < fNruns) {
  329.                                         // Shift up item data
  330.         ::MemMove( getRunItemPtr(inRunIndex + 1), getRunItemPtr(inRunIndex + 3),
  331.                         (fNruns - inRunIndex - 1) * fValueSize);
  332.                                         // Shift up RunRecords
  333.         ::MemMove(fRuns + (inRunIndex + 1) * sizeof(RunRec),
  334.                         fRuns + (inRunIndex + 3) * sizeof(RunRec),
  335.                         (fNruns - inRunIndex - 1) * sizeof(RunRec));
  336.         }
  337.                                         // Store data for new items
  338.     ::MemMove(inItem, getRunItemPtr(inRunIndex + 1), fValueSize);
  339.                                         // Copy data for second half of split run
  340.     ::MemMove( getRunItemPtr(inRunIndex), getRunItemPtr(inRunIndex + 2), fValueSize);
  341.     
  342.     long    secondSplitRange = run[inRunIndex].end - inItemIndex;
  343.     run[inRunIndex].end = inItemIndex - 1;
  344.     run[inRunIndex+1].start = inItemIndex;
  345.     run[inRunIndex+1].end = inItemIndex + inCount - 1;
  346.     run[inRunIndex+2].start = run[inRunIndex+1].end + 1;
  347.     run[inRunIndex+2].end = run[inRunIndex+2].start + secondSplitRange;
  348.     
  349.                                         // Shift up indexes of Runs past insertion point
  350.     fNruns += 2;
  351.     for (long i = inRunIndex + 3; i < fNruns; i++) {
  352.         run[i].start += inCount;
  353.         run[i].end += inCount;
  354.         }
  355. }
  356.  
  357.  
  358.  
  359. void DRunArray::ExtendRun( long    inRunIndex, long inCount)
  360. {
  361.     RunRec    *run = (RunRec*) fRuns;
  362.     run[inRunIndex].end += inCount;
  363.                                         // Shift up indexes of Runs past insertion point
  364.     for (long i = inRunIndex + 1; i < fNruns; i++) {
  365.         run[i].start += inCount;
  366.         run[i].end += inCount;
  367.         }
  368. }
  369.